高速缓存的22 个基础知识
AP SHANTHI博士
本模块的目标是讨论高速缓存的基础知识。我们将讨论各种映射策略，也会讨论读/写策略。基本上，将回答关于块放置、块识别、块替换和写入策略的四个主要问题。
与现代处理器的速度相比，主存储器的速度非常低。为了获得良好的性能，处理器不能花太多时间等待访问主存储器中的指令和数据。因此，设计一种减少访问必要信息所需时间的方案非常重要。由于主存储器单元的速度受电子和封装约束的限制，因此必须在不同的架构安排中寻求解决方案。一个有效的解决方案是使用快速缓存内存，这本质上使主存储器在处理器看来比实际速度更快。缓存是一种更小、速度更快的内存，用于存储来自最常用主内存位置的数据副本。只要大多数内存访问都是缓存内存位置，内存访问的平均延迟将更接近缓存延迟而不是主内存的延迟。
缓存机制的有效性基于称为引用局部性的计算机程序属性。对程序的分析表明，它们的大部分执行时间都花在了重复执行许多指令的例程上。这些指令可能构成一个简单的循环、嵌套循环或几个相互重复调用的过程。指令排序的实际详细模式并不重要——关键是程序局部区域中的许多指令在某个时间段内重复执行，而程序的其余部分被访问的频率相对较低。这称为参考位置。它表现在两个方面：时间和空间。第一个意思是最近执行的指令很可能很快就会再次执行。空间方面意味着与最近执行的指令（相对于指令的地址）非常接近的指令也可能很快被执行。
如果程序的活动段可以放置在快速缓存中，那么总执行时间可以显着减少。从概念上讲，高速缓存的操作非常简单。存储器控制电路被设计为利用参考局部性的特性。参考位置的时间方面表明，无论何时首次需要信息项（指令或数据），都应将该项 放入缓存中，希望它会一直保留到再次需要时。空间方面表明，与其仅从主内存中将一项提取到缓存中，还不如提取位于相邻地址的多个项目。我们将使用术语块指一组具有某种大小的连续地址位置。另一个经常用来指代缓存块的术语是缓存线。
包含在存储器层次结构中的高速缓存可以是拆分的或统一的/双的。拆分缓存是一种我们拥有单独的数据缓存和单独的指令缓存的缓存。在这里，两个缓存并行工作，一个传输数据，另一个传输指令。双缓存或统一缓存是其中数据和指令存储在同一缓存中。总大小等于两个拆分缓存总和的组合缓存通常具有更好的命中率。之所以会出现这种较高的速率，是因为组合高速缓存没有严格划分指令可能使用的条目数与数据可能使用的条目数。尽管如此，许多处理器使用拆分指令和数据缓存来增加缓存带宽。
当收到来自处理器的读请求时，包含指定位置的内存字块的内容被传输到缓存中。随后，当程序引用该块中的任何位置时，直接从缓存中读取所需的内容。通常，高速缓存可以在任何给定时间存储合理数量的块，但与主内存中的块总数相比，这个数字很小。主存块和缓存中的块之间的对应关系由映射函数指定。当缓存已满并且引用了不在缓存中的内存字（指令或数据）时，缓存控制硬件必须决定应该删除哪个块，以便为包含所引用字的新块创建空间。用于做出此决定的规则集合构成了替换算法。
因此，在高速缓存中要处理的三个主要问题是
· 缓存放置——你将块放在缓存中的什么位置？
· 缓存识别——如何识别所请求的信息在缓存中是否可用？
· 缓存替换——缓存中的哪个块将被替换，为传入的块让路？
这些问题以1MB大小的主存（主存地址为20位）、大小为2KB的缓存和64字节的块大小来回答和解释。由于块大小为 64 字节，因此您可以立即识别出主内存有 214 块，缓存有 25 块。也就是说，主存的 16K 块必须映射到缓存的 32 块。使用了三种不同的 映射策略——直接映射、完全关联映射和 n 路集关联映射。它们将在下面讨论。
直接映射：这是最简单的映射技术。在这种技术中，主内存的块 i 被映射到块 j 模（缓存中的块数）的缓存。在我们的例子中，它是块 j mod 32。也就是说，主内存的前 32 个块映射到相应的 32 个缓存块，0 到 0，1 到 1，……和 31 到 31。记住我们有缓存中只有 32 个块。因此，接下来的 32 个主内存块也映射到相同的相应缓存块上。因此，32 再次映射到缓存中的块 0，33 映射到缓存中的块 1，依此类推。也就是说，主内存块被分组为 32 个块的组，这些组中的每一个都将映射到相应的缓存块。例如，每当主内存块 0, 32, 64, ... 中的一个被加载到缓存中时，它只存储在缓存块 0 中。因此，在任何时间点，如果某个其他块正在占用缓存块，删除并存储另一个块。例如，如果我们要引入第 64 块，并且块 0 已经在缓存中可用，块 0 被移除，块 64 被引入。类似地，块 1、33、65、……存储在缓存块 1 中，依此类推。您可以很容易地看到 29 个主内存块将映射到缓存中的同一块上。由于多个内存块被映射到给定的缓存块位置，即使缓存未满，该位置也可能出现争用。也就是说，有权占用同一缓存块的块可能会竞争该块。例如，如果处理器交替引用来自块 0 和 32 的指令，即使缓存未满，也会发生冲突。通过允许新块覆盖当前驻留块来解决争用。因此，在这种情况下，替换算法是微不足道的。没有其他地方可以容纳该街区。
块在缓存中的位置由内存地址决定。内存地址可以分为三个字段，如图 26.1 所示。低 6 位选择块中的 64 个字之一。当一个新块进入缓存时，5 位缓存块字段决定了该块必须存储在的缓存位置。块内存地址的高 9 位存储在与其在缓存中的位置相关联的 9 个标记位中。它们标识有资格映射到该缓存位置的 29 个块中的哪些当前驻留在缓存中。生成主存地址后，首先检查块字段。这将指向您必须检查的块。现在检查标签字段。如果它们匹配，则块在缓存中可用并且命中。否则，就是错过了。然后，包含所需字的块必须首先从主内存中读取并加载到缓存中。识别块后，使用单词字段获取 64 个单词之一。请注意，单词字段不参与映射。
标签 堵塞 单词
9 5 6
图 26.1 直接映射
考虑一个地址 78F28，它是 0111 1000 1111 0010 1000。现在检查该块是否在缓存中，将其拆分为三个字段，分别为 011110001 11100 101000。块字段表示您必须检查块 28。现在检查九个位标记字段。如果它们匹配，那就是成功。
直接映射技术很容易实现。要检查的标签条目的数量只有一个，标签字段的长度也更少。替换算法非常简单。但是，它不是很灵活。即使缓存未满，由于严格的映射策略，您可能不得不在主内存和缓存之间进行大量抖动。
全关联映射：这是一种更加灵活的映射方法，其中一个主内存块可以放置在任何缓存块位置。这表明不需要块字段。在这种情况下，当内存块驻留在缓存中时，需要 14 个标签位来标识内存块。如图 5.8 所示。将从处理器接收到的地址的标记位与高速缓存的每个块的标记位进行比较，以查看是否存在所需的块。这称为关联映射技术。它在选择放置内存块的缓存位置方面提供了完全的自由。因此，可以更有效地使用缓存中的空间。只有当缓存已满时，必须将新块放入缓存中才能替换（弹出）现有块。在这种情况下，我们需要一个算法来选择要替换的块。常用的算法有随机、先进先出和LRU。随机替换会随机选择要删除的块。FIFO 删除最旧的块，而不考虑内存访问模式。所以，它不是很有效。另一方面，最近最少使用的技术会考虑访问模式并删除最长时间未被引用的块。这是非常有效的。
因此，关联映射是完全灵活的。但是，关联缓存的成本高于直接映射缓存的成本，因为需要搜索所有标签模式以确定给定的块是否在缓存中。这应该是前一节中讨论的关联搜索。另外，请注意标签长度会增加。即，标签的数量和标签长度都增加。更换也很复杂。因此，它在实践中是不可行的。
标签 单词
14 6
图 26.2 全关联映射
设置关联映射： 这是上述两种技术之间的折衷。缓存的块被分组为集合，由 n 个块组成，并且映射允许主存储器的块驻留在特定集合的任何块中。它也称为 n 路集关联映射。因此，通过为块放置提供一些选择，可以缓解直接方法的争用问题。同时，通过减小关联搜索的大小来降低硬件成本。对于我们的示例，集合关联映射技术的主内存地址如图 26.3 所示，用于每个集合有两个块的缓存（2 路集合关联映射）。缓存中有 16 个集合。在这种情况下，内存块 0、16、32……映射到缓存集 0，并且它们可以占用该集内的两个块位置中的任何一个。有 16 个集合意味着地址的 4 位集合字段决定了缓存的哪一个集合可能包含所需的块。然后必须将地址的 11 位标记字段与该组的两个块的标记相关联地进行比较，以检查是否存在所需的块。这种双向关联搜索实现起来很简单，并且结合了其他两种技术的优点。这实际上可以视为一般情况；当n为1时，变为直接映射；当 n 是缓存中的块数时，它是关联映射。这种双向关联搜索实现起来很简单，并且结合了其他两种技术的优点。这实际上可以视为一般情况；当n为1时，变为直接映射；当 n 是缓存中的块数时，它是关联映射。这种双向关联搜索实现起来很简单，并且结合了其他两种技术的优点。这实际上可以视为一般情况；当n为1时，变为直接映射；当 n 是缓存中的块数时，它是关联映射。
标签 放 单词
11 4 6
图 26.3 集合关联映射
多一个控制位，称为有效位，必须为每个块提供。该位指示块是否包含有效数据。它不应与前面提到的修改或脏位混淆。脏位指示块在其缓存驻留期间是否已被修改，仅在不使用直写方法的系统中才需要。当系统最初通电或主存储器加载了来自磁盘的新程序和数据时，有效位都设置为 0。从磁盘到主存储器的传输是通过 DMA 机制进行的。通常，出于成本和性能原因，它们会绕过缓存。特定缓存块的有效位在第一次从主内存加载该块时设置为 1，每当主内存块被绕过缓存的源更新时， 缓存。如果是，则将其有效位清除为 0。这可确保缓存中不存在陈旧数据。
当 DMA 传输是从主内存到磁盘，并且缓存使用回写协议时，也会出现类似的困难。在这种情况下，内存中的数据可能不会反映可能在缓存副本中所做的更改。此问题的一种解决方案是通过在 DMA 传输发生之前强制将脏数据写回内存来刷新缓存。操作系统可以很容易地做到这一点，并且不会对性能产生很大的影响，因为这种磁盘传输并不经常发生。这种需要确保两个不同的实体（在这种情况下是处理器和 DMA 子系统）使用相同的数据副本被称为缓存一致性问题。
读/写策略：最后，我们还需要讨论所遵循的读/写策略。处理器不需要明确知道缓存的存在。它只是使用引用内存中位置的地址发出读取和写入请求。高速缓存控制电路确定所请求的字当前是否存在于高速缓存中。如果是，则在适当的缓存位置上执行读取或写入操作。在这种情况下，可以说发生了读 或 写命中。在读操作中，不会发生任何修改，因此主存储器不受影响。对于写命中，系统可以通过两种方式进行。在第一种技术中，称为直写协议，缓存位置和主存位置同时更新。第二种技术是仅更新缓存位置，并使用相关联的标志位将其标记为已更新，通常称为脏 位或 修改位。当包含该标记字的块从高速缓存中移除以为新块腾出空间时，字的主存储器位置稍后更新。这种技术称为回写 或 复写协议。直写协议更简单，但当给定的缓存字在其缓存驻留期间多次更新时，它会导致主存储器中不必要的写入操作。请注意，回写协议也可能导致不必要的写操作，因为当一个缓存块被写回内存时，该块的所有字都会被写回，即使该块在缓存中时只有一个字发生了变化. 如果您为每个块维护更多数量的脏位，则可以避免这种情况。在写操作期间，如果寻址字不在缓存中，则写未命中发生。然后，如果使用直写协议，则将信息直接写入主存储器。在回写协议的情况下，包含寻址字的块首先被带入缓存，然后缓存中所需的字被新信息覆盖。
当发生写未命中时，我们使用写分配策略或不写分配策略。也就是说，如果我们对写命中使用回写策略，那么块无论如何都会被带到缓存（写分配）并设置脏位。另一方面，如果使用的是直写 策略，则该块不会分配给缓存，并且修改会立即发生在主内存中。
不管使用何种写策略，处理器通常使用写缓冲区来允许缓存在数据放入缓冲区后立即处理，而不是等到数据真正写入主内存。
总而言之，我们已经讨论了对高速缓存的需求。我们已经研究了与高速缓存相关的各种问题，即放置策略、替换策略和读/写策略。直接映射是最容易实现的。在直接映射缓存中，缓存块在确定是命中还是未命中之前可用，因为可以假设命中并在未命中时继续并稍后恢复。与用于 n 路集关联映射的 N 个比较器相比，它还只需要一个比较器。在集合关联映射的情况下，数据有一个额外的 MUX 延迟，数据只有在确定它是命中还是未命中后才出现。但是，可以通过并行比较集合中的所有标签并根据标签结果选择数据来加快操作速度。集合关联映射比直接映射更灵活。全关联映射最灵活，但实现起来也最复杂，很少使用。
网页链接/支持材料
计算机组织与设计——硬件/软件接口，David A. Patterson 和 John L. Hennessy，第 4 版，Morgan Kaufmann，Elsevier，2009 年。
Computer Architecture – A Quantitative Approach，John L. Hennessy 和 David A.Patterson，第 5 版，Morgan Kaufmann，Elsevier，2011。
计算机组织，Carl Hamacher、Zvonko Vranesic 和 Safwat Zaky，第 5 版，McGraw-Hill 高等教育，2011 年。